package greddy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class _15_56_合并区间 {
    public static int[][] merge(int[][] intervals) {
    	Arrays.sort(intervals,new Comparator() {
			@Override
			public int compare(Object o1, Object o2) {
				int[] i = (int[])o1;
				int[] j = (int[])o2;
				Integer a = i[0];
				Integer b = j[0];
				return a.compareTo(b);
			}
    	});
    	Map<Integer,Integer> map = new HashMap<>();
    	for(int i = 1; i <= intervals.length; i++) {
    		// 当前元素左区间大于前元素的右区间，说明不在前一个元素区间范围内
    		if(i == intervals.length || intervals[i][0] > intervals[i-1][1]) {
    			map.put(intervals[i-1][0], intervals[i-1][1]);
    		} else {
    			intervals[i][0] = Math.min(intervals[i][0], intervals[i-1][0]);
    			intervals[i][1] = Math.max(intervals[i][1], intervals[i-1][1]);
    		}
    	}
    	int arr[][] = new int[map.size()][2];
    	int index = 0;
    	for (Entry<Integer, Integer> m: map.entrySet()) {
    		arr[index][0] = m.getKey();
    		arr[index][1] = m.getValue();
    		index++;
		}
    	
    	for(int i = 0 ; i < arr.length ; i++) {
    		System.out.println(arr[i][0] + " " + arr[i][1]);
    	}
    	
    	return arr;
    }
    
    public static void main(String[] args) {
    	int[][] intervals = {{1,4},{4,5}};
    	merge(intervals);
	}
}
